/*
 * Copyright (C) 2002 Roberto Micarelli
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
 */

/*
 * best view tabstop=4
 */

#ifndef _DGL_GRAPH_H_
#define _DGL_GRAPH_H_

#ifdef DGL_STATS
#include <time.h>
#endif

#include "heap.h"
#include "tree.h"

/*
 * Graph State bitmask - returned by dglGet_State() function
 */
#define DGL_GS_FLAT			0x1		/* otherwise is TREE */

/*
 * Graph Family
 */
#define DGL_GF_COMPLETE		0x1
#define DGL_GF_BIPARTITE	0x2
#define DGL_GF_REGULAR		0x4
#define DGL_GF_BOUQUET		0x8
#define DGL_GF_DIPOLE		0x10
#define DGL_GF_PATH			0x20
#define DGL_GF_CYCLE		0x40

/*
 * Graph Options
 */
#define DGL_GO_EdgePrioritize_COST	0x10
#define DGL_GO_EdgePrioritize_ATTR	0x20
#define DGL_GO_NodePrioritize_ATTR	0x40


/*
 * Node Status bitmask - returned by dglNodeGet_Status()
 */
#define DGL_NS_HEAD			0x1		/* node exists as at least one edge's head (static) */
#define DGL_NS_TAIL			0x2		/* node exists as at least one edge's tail (static) */
#define DGL_NS_ALONE		0x4		/* node is a component */


/*
 * Edge Status bitmask - returned by dglEdgeGet_Status()
 */
#define DGL_ES_DIRECTED		0x1		/* force edge to be directed */


/*
 * Endianess Values - returned by dglGet_Endianess() function
 */
#define DGL_ENDIAN_BIG		1
#define DGL_ENDIAN_LITTLE	2


/*
 * miscellaneous
 */
/* add-edge/add-node flags */
#define DGL_STRONGCONNECT	0x1
#define DGL_ALONE			0x2
#define DGL_MERGE_EDGE		0x4
/* */



/*
 * Shortest Path clip definitions
 */
typedef struct _dglSPClipInput
{
	dglInt32_t * 	pnPrevEdge;
	dglInt32_t * 	pnNodeFrom;
	dglInt32_t * 	pnEdge;
	dglInt32_t * 	pnNodeTo;
	dglInt32_t		nFromDistance;

} dglSPClipInput_s;

typedef struct _dglSPClipOutput
{
	dglInt32_t		nEdgeCost;

} dglSPClipOutput_s;


/*
 * Spanning clip definitions
 */
typedef struct _dglSpanClipInput
{
	dglInt32_t *		pnNodeFrom;
	dglInt32_t *		pnEdge;
	dglInt32_t *		pnNodeTo;

} dglSpanClipInput_s;

typedef struct _dglSpanClipOutput
{
	dglInt32_t *		pnReserved;

} dglSpanClipOutput_s;


struct dglGraph;

/*
 * Node Prioritizer
 */
typedef struct {
	void * pvAVL;
} dglNodePrioritizer_s;

/*
 * Edge Prioritizer
 */
typedef struct {
	int cEdge;
	int iEdge;
	dglTreeEdgePri32_s * pEdgePri32Item;
	void * pvAVL;
} dglEdgePrioritizer_s;


/*
 * The graph context
 */
typedef struct _dglGraph
{
	int					iErrno;

	dglByte_t			Version;
	dglByte_t			Endian;
	dglInt32_t			NodeAttrSize;
	dglInt32_t			EdgeAttrSize;
	dglInt32_t			aOpaqueSet[ 16 ];

	dglInt32_t			cNode;
	dglInt32_t			cHead;
	dglInt32_t			cTail;
	dglInt32_t			cAlone;
	dglInt32_t			cEdge;
	dglInt64_t			nnCost;

	dglInt32_t			Flags;
	dglInt32_t			nFamily;
	dglInt32_t			nOptions;

	void *				pNodeTree;
	void *				pEdgeTree;
	dglByte_t * 			pNodeBuffer;
	dglInt32_t			iNodeBuffer;
	dglByte_t * 			pEdgeBuffer;
	dglInt32_t			iEdgeBuffer;


	dglEdgePrioritizer_s edgePrioritizer;
	dglNodePrioritizer_s nodePrioritizer;


/* so far statistics are only computed by dglAddEdge() */
#ifdef DGL_STATS
	clock_t				clkAddEdge;  /* cycles spent during the last addedge execution */
	int					cAddEdge;    /* # of calls to dglAddEdge() */
	clock_t				clkNodeTree; /* cycles spent in accessing the node binary tree */
	int					cNodeTree;   /* # of probes in the node tree */
#endif
}
dglGraph_s;

/*
 * Shortest Path clip function type
 */
typedef int (*dglSPClip_fn)(dglGraph_s *, dglSPClipInput_s *, dglSPClipOutput_s *, void *);

/*
 * Spanning clip function type
 */
typedef int (*dglSpanClip_fn)(dglGraph_s *, dglGraph_s *, dglSpanClipInput_s *, dglSpanClipOutput_s *, void *);

/*
 * An ARC defined as : from-node, to-node, edge pointer, to-node-distance (from the path starting node)
 */
typedef struct _dglSPArc
{
	dglInt32_t nFrom;
	dglInt32_t nTo;
	dglInt32_t *	pnEdge;
	dglInt32_t nDistance;
}
dglSPArc_s;

/*
 * Shortest Path Report
 */
typedef struct _dglSPReport
{
	dglInt32_t		nStartNode;
	dglInt32_t		nDestinationNode;
	dglInt32_t		nDistance;
	dglInt32_t		cArc;
	dglSPArc_s *	pArc;
}
dglSPReport_s;

/*
 * Shortest Path Cache
 */
typedef struct {
	dglInt32_t	nStartNode;
	dglHeap_s	NodeHeap;
	void * 		pvVisited;	
	void * 		pvPredist;	
}
dglSPCache_s;

/*
 * Node Traverser
 */
typedef struct {
	dglGraph_s *		pGraph;
	void *				pvAVLT;
	dglInt32_t * 		pnNode;
} dglNodeTraverser_s;

/*
 * Edgeset Traverser
 */
typedef struct {
	dglGraph_s *		pGraph;
	dglInt32_t *			pnEdgeset;
	void *				pvCurrentItem;
	int					cEdge, iEdge;
} dglEdgesetTraverser_s;

/*
 * Edge Traverser
 */
typedef struct {
	dglGraph_s * pGraph;
	void * pvAVLT;
	dglInt32_t *	pnEdge;
	dglEdgePrioritizer_s * pEdgePrioritizer;
} dglEdgeTraverser_s;


/*
 * Error codes returned by dglError
 */
#define DGL_ERR_BadVersion 				1
#define DGL_ERR_BadNodeType 			2
#define DGL_ERR_MemoryExhausted 		3
#define DGL_ERR_HeapError 				4
#define DGL_ERR_UndefinedMethod 		5
#define DGL_ERR_Write 					6
#define DGL_ERR_Read 					7
#define DGL_ERR_NotSupported 			8
#define DGL_ERR_UnknownByteOrder 		9
#define DGL_ERR_HeadNodeNotFound 		10
#define DGL_ERR_TailNodeNotFound 		11
#define DGL_ERR_BadEdge 				12
#define DGL_ERR_BadOnFlatGraph			13
#define DGL_ERR_BadOnTreeGraph			14
#define DGL_ERR_NodeNotFound 			15
#define DGL_ERR_TreeSearchError 		16
#define DGL_ERR_UnexpectedNullPointer 	17
#define DGL_ERR_VersionNotSupported		18
#define DGL_ERR_EdgeNotFound			19
#define DGL_ERR_NodeAlreadyExist		20
#define DGL_ERR_NodeIsAComponent		21
#define DGL_ERR_EdgeAlreadyExist		22
#define DGL_ERR_BadArgument				23



/*
 * graph context management
 */
int  dglInitialize(dglGraph_s * pGraph, dglByte_t Version, dglInt32_t NodeAttrSize, dglInt32_t EdgeAttrSize, dglInt32_t * pOpaqueSet);
int  dglRelease( dglGraph_s * pGraph );
int  dglUnflatten( dglGraph_s * pGraph );
int  dglFlatten( dglGraph_s * pGraph );
void dglResetStats( dglGraph_s * pgraph );

/*
 * node management
 */
dglInt32_t * dglGetNode(dglGraph_s * pGraph , dglInt32_t nNodeId);
int 		dglAddNode(
               dglGraph_s * 	pGraph ,
               dglInt32_t 		nNodeId ,
               void *			pvNodeAttr ,
               dglInt32_t		nFlags
            );
int			dglDelNode(
               dglGraph_s * 	pGraph ,
               dglInt32_t 		nNodeId
			);
dglInt32_t	dglNodeGet_Id(dglGraph_s * pGraph, dglInt32_t * pnNode);
dglInt32_t *	dglNodeGet_OutEdgeset(dglGraph_s * pGraph, dglInt32_t * pnNode);
dglInt32_t *	dglNodeGet_InEdgeset(dglGraph_s * pGraph, dglInt32_t * pnNode);
dglInt32_t	dglNodeGet_Status(dglGraph_s * pGraph, dglInt32_t * pnNode);
dglInt32_t *	dglNodeGet_Attr(dglGraph_s * pGraph, dglInt32_t * pnNode);
void        dglNodeSet_Attr(dglGraph_s * pGraph, dglInt32_t * pnNode, dglInt32_t * pnAttr);
int			dglNodeGet_InDegree(dglGraph_s * pGraph, dglInt32_t * pnNode);
int			dglNodeGet_OutDegree(dglGraph_s * pGraph, dglInt32_t * pnNode);
int			dglNodeGet_Valence(dglGraph_s * pGraph, dglInt32_t * pnNode);

/*
 * edge management
 */
dglInt32_t 	dglEdgesetGet_EdgeCount(dglGraph_s * pGraph, dglInt32_t * pnOutEdgeset);

dglInt32_t   dglEdgeGet_Id(dglGraph_s * pGraph , dglInt32_t * pnEdge );
dglInt32_t   dglEdgeGet_Cost(dglGraph_s * pGraph , dglInt32_t * pnEdge );
dglInt32_t * dglEdgeGet_Head(dglGraph_s * pGraph , dglInt32_t * pnEdge );
dglInt32_t * dglEdgeGet_Tail(dglGraph_s * pGraph , dglInt32_t * pnEdge );
dglInt32_t * dglEdgeGet_Attr(dglGraph_s * pGraph , dglInt32_t * pnEdge );
int         dglEdgeSet_Attr(dglGraph_s * pGraph , dglInt32_t * pnAttr , dglInt32_t * pnEdge );

dglInt32_t *	dglGetEdge(
               dglGraph_s * 	pGraph ,
               dglInt32_t 		nEdgeId
		   );

int         dglDelEdge(
               dglGraph_s * 	pGraph ,
               dglInt32_t 		nEdgeId
		   );

int         dglAddEdge(
               dglGraph_s * 	pGraph ,
               dglInt32_t 		nHead ,
               dglInt32_t 		nTail ,
               dglInt32_t 		nCost ,
               dglInt32_t 		nEdge
            );

int         dglAddEdgeX(
               dglGraph_s * 	pGraph ,
               dglInt32_t 		nHead ,
               dglInt32_t 		nTail ,
               dglInt32_t 		nCost ,
               dglInt32_t 		nEdge ,
               void *			pvFnodeAttr ,
               void *			pvTnodeAttr ,
               void *			pvEdgeAttr ,
               dglInt32_t		nFlags
            );


/*
 * graph I/O
 */
int dglWrite( dglGraph_s * pGraph, int fd );
int dglRead( dglGraph_s * pGraph, int fd );

typedef struct {
	dglGraph_s * pG;
	int nState;
	int fSwap;
	int cb;
	int ib;
	unsigned char * pb;
	unsigned char   ab[118]; /* 118 = graph header size */
} dglIOContext_s;

int dglIOContextInitialize(dglGraph_s *, dglIOContext_s *);
void dglIOContextRelease(dglIOContext_s *);

/*
 * Chunked Write callback function type
 */
typedef int (*dglWriteChunk_fn)( dglGraph_s *, unsigned char * pbChunk, int cbChunk, void * pvArg );

int dglWriteChunk(dglIOContext_s *, dglWriteChunk_fn, void * pvArg);
int dglReadChunk(dglIOContext_s *, dglByte_t * pbChunk, int cbChunk);



/*
 * Algorithms
 */
int dglShortestPath(
                     dglGraph_s *     pGraph,
					 dglSPReport_s ** ppReport,
                     dglInt32_t 		  nStartNode,
                     dglInt32_t 		  nDestinationNode,
                     dglSPClip_fn	  fnClip,
                     void *			  pvClipArg,
					 dglSPCache_s *   pCache
                  );
int dglShortestPathGraph(
                     dglGraph_s *   pGraph,
                     dglGraph_s *   pGraphOut,
                     dglInt32_t 	    nStartNode,
                     dglInt32_t 	    nDestinationNode,
                     dglSPClip_fn   fnClip,
                     void *		    pvClipArg,
					 dglSPCache_s * pCache
                  );
int dglShortestDistance(
                     dglGraph_s * pGraph,
                     dglInt32_t *  pnDistance,
                     dglInt32_t 	  nStartNode,
                     dglInt32_t 	  nDestinationNode,
                     dglSPClip_fn fnClip,
                     void *		  pvClipArg,
					 dglSPCache_s * pCache
                  );
int dglShortestDistanceGraph(
                     dglGraph_s *   pGraph,
                     dglGraph_s *   pGraphOut,
                     dglInt32_t 		  nStartNode,
                     dglInt32_t 		  nDestinationNode,
                     dglSPClip_fn	  fnClip,
                     void *			  pvClipArg,
					 dglSPCache_s * pCache
                  );

int dglInitializeSPCache( dglGraph_s * pgraph, dglSPCache_s * pCache );
void dglReleaseSPCache	( dglGraph_s * pgraph, dglSPCache_s * pCache );
void dglFreeSPReport	( dglGraph_s * pGraph , dglSPReport_s * pSPReport );

int	dglDepthSpanning(
       dglGraph_s *  	pgraphInput,
       dglGraph_s *  	pgraphOutput,
       dglInt32_t		nVertexNode,
       dglSpanClip_fn	fnClip,
       void *			pvClipArg
    );

int dglDepthComponents(
       dglGraph_s *  	pgraphInput,
       dglGraph_s *  	pgraphComponents,
       int				cgraphComponents,
       dglSpanClip_fn	fnClip,
       void *			pvClipArg
    );

int	dglMinimumSpanning(
       dglGraph_s *  	pgraphInput,
       dglGraph_s *  	pgraphOutput,
       dglInt32_t		nVertexNode,
       dglSpanClip_fn	fnClip,
       void *			pvClipArg
    );

/*
 * error management
 */
int    dglErrno( dglGraph_s * pgraph );
char * dglStrerror( dglGraph_s * pgraph );

/*
 * graph property hiders
 */
int	        dglGet_Version      (dglGraph_s * pGraph);
void        dglSet_Version      (dglGraph_s * pGraph, int Version);
int	        dglGet_Endianess    (dglGraph_s * pGraph);
int	        dglGet_NodeAttrSize (dglGraph_s * pGraph);
int	        dglGet_EdgeAttrSize (dglGraph_s * pGraph);
int	        dglGet_NodeCount    (dglGraph_s * pGraph);
int	        dglGet_HeadNodeCount(dglGraph_s * pGraph);
int	        dglGet_TailNodeCount(dglGraph_s * pGraph);
int	        dglGet_AloneNodeCount(dglGraph_s * pGraph);
int	        dglGet_EdgeCount    (dglGraph_s * pGraph);
int	        dglGet_State   		(dglGraph_s * pGraph);
dglInt32_t * dglGet_Opaque	    (dglGraph_s * pGraph);
void        dglSet_Opaque       (dglGraph_s * pGraph, dglInt32_t * pOpaque);
int			dglGet_NodeSize     (dglGraph_s * pGraph);
int			dglGet_EdgeSize     (dglGraph_s * pGraph);
dglInt64_t  dglGet_Cost         (dglGraph_s * pGraph);
void        dglSet_Cost         (dglGraph_s * pGraph, dglInt64_t nnCost);
dglInt32_t	dglGet_Family       (dglGraph_s * pGraph);
void        dglSet_Family       (dglGraph_s * pGraph, dglInt32_t nFamily);
dglInt32_t	dglGet_Options      (dglGraph_s * pGraph);
void        dglSet_Options      (dglGraph_s * pGraph, dglInt32_t nOptions);
dglEdgePrioritizer_s * dglGet_EdgePrioritizer(dglGraph_s * pGraph);
dglNodePrioritizer_s * dglGet_NodePrioritizer(dglGraph_s * pGraph);


/*
 * node traverser
 */
int 		dglNode_T_Initialize( dglNodeTraverser_s * pTraverser , dglGraph_s * pGraph );
void 		dglNode_T_Release	( dglNodeTraverser_s * pTraverser );
dglInt32_t *dglNode_T_First		( dglNodeTraverser_s * pTraverser );
dglInt32_t *dglNode_T_Last		( dglNodeTraverser_s * pTraverser );
dglInt32_t *dglNode_T_Next 		( dglNodeTraverser_s * pTraverser );
dglInt32_t *dglNode_T_Prev 		( dglNodeTraverser_s * pTraverser );
dglInt32_t *dglNode_T_Find 		( dglNodeTraverser_s * pTraverser , dglInt32_t nNodeId );


/*
 * edgeset traverser
 */
int			dglEdgeset_T_Initialize	(
									dglEdgesetTraverser_s * pTraverser ,
									dglGraph_s * pGraph ,
									dglInt32_t * pnEdgeset
									);
void		dglEdgeset_T_Release	( dglEdgesetTraverser_s * pTraverser );
dglInt32_t *dglEdgeset_T_First		( dglEdgesetTraverser_s * pTraverser );
dglInt32_t *dglEdgeset_T_Next		( dglEdgesetTraverser_s * pTraverser );


/*
 * edge traverser
 */
int 		dglEdge_T_Initialize	(
									dglEdgeTraverser_s * pTraverser ,
									dglGraph_s * pGraph ,
									dglEdgePrioritizer_s * pEdgePrioritizer
									);
void 		dglEdge_T_Release		( dglEdgeTraverser_s * pTraverser );
dglInt32_t *dglEdge_T_First			( dglEdgeTraverser_s * pTraverser );
dglInt32_t *dglEdge_T_Next			( dglEdgeTraverser_s * pTraverser );

#endif
